package com.nowcoder.topic.string.simple;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * NC31 第一个只出现一次的字符
 * @author d3y1
 */
public class NC31{
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return int整型
     */
    public int FirstNotRepeatingChar (String str) {
        return solution1(str);
        // return solution2(str);
        // return solution3(str);
    }

    /**
     * HashSet
     * @param str
     * @return
     */
    private int solution1(String str){
        int len = str.length();
        HashSet<Character> existedSet = new HashSet<>();
        char ch;
        for(int i=0; i<len; i++){
            ch = str.charAt(i);
            if(!existedSet.contains(ch)){
                existedSet.add(ch);
                if(i == len-1){
                    return i;
                }else{
                    if(str.substring(i+1).indexOf(ch) == -1){
                        return i;
                    }
                }
            }
        }

        return -1;
    }

    /**
     * 数组
     * @param str
     * @return
     */
    private int solution2(String str){
        // z -> 122
        int[] count = new int[123];
        for(char ch: str.toCharArray()){
            count[ch]++;
        }

        for(int i=0; i<str.length(); i++){
            if(count[str.charAt(i)] == 1){
                return i;
            }
        }

        return -1;
    }

    /**
     * HashMap + Queue
     * @param str
     * @return
     */
    private int solution3(String str){
        HashMap<Character, Integer> positionMap = new HashMap<>();
        Queue<Character> queue = new LinkedList<>();
        Integer position;
        char ch;
        for(int i=0; i<str.length(); i++){
            ch = str.charAt(i);
            if(positionMap.containsKey(ch)){
                positionMap.put(ch, -1);
            }else{
                positionMap.put(ch, i);
                queue.offer(ch);
            }
        }

        while(!queue.isEmpty() && positionMap.get(queue.peek())==-1){
            queue.poll();
        }

        if(queue.isEmpty()){
            return -1;
        }else{
            return positionMap.get(queue.peek());
        }
    }

    /**
     * HashMap
     * @param str
     * @return
     */
    private int solution4(String str){
        HashMap<Character, Integer> countMap = new HashMap<>();
        for(char ch: str.toCharArray()){
            countMap.put(ch, countMap.getOrDefault(ch, 0)+1);
        }

        for(int i=0; i<str.length(); i++){
            if(countMap.get(str.charAt(i)) == 1){
                return i;
            }
        }

        return -1;
    }
}